home *** CD-ROM | disk | FTP | other *** search
/ Java Programmer's Toolkit / Java Programmer's Toolkit.iso / applets / collectn / incrimpl.jav < prev    next >
Encoding:
Text File  |  1995-12-14  |  11.6 KB  |  411 lines
  1. /*
  2.   File: IncrImpl.java
  3.  
  4.   Originally written by Doug Lea and released into the public domain. 
  5.   Thanks for the assistance and support of Sun Microsystems Labs, Agorics 
  6.   Inc, Loral, and everyone contributing, testing, and using this code.
  7.  
  8.   History:
  9.   Date     Who                What
  10.   24Sep95  dl@cs.oswego.edu   Create from collections.java  working file
  11.   Thu Oct 12 1995 Doug Lea    Remove special no-copy on enum clone
  12.   13Oct95  dl                 New strategy to check if pinned by enumerator
  13. */
  14.   
  15. package collections;
  16.  
  17. import java.util.Enumeration;
  18. import java.util.NoSuchElementException;
  19.  
  20. /**
  21.  *
  22.  *
  23.  * Base class for  Immutable Collection implementations.
  24.  * using `negative deltas'. That is, they update
  25.  * an internally held Collection and set it as the internal Collection
  26.  * for the Immutable Collection serving as the result, but also keep
  27.  * a record of how to undo this change on a copy of the update, so
  28.  * as to reconstruct the original Collection.
  29.  * <P>
  30.  * Since it's usually the case that applications use updates
  31.  * rather than their sources, negative deltas are generally
  32.  * more efficient than other schemes. Also, because updates don't
  33.  * point to their sources, when a source becomes unreferenced,
  34.  * it and all of its edit records can be garbage collected.
  35.  * The price you pay for these nice aspects is that
  36.  * reconstruction of old versions is not always all that fast or cheap.
  37.  * <P>
  38.  * The logic of reconstruction is to work our way to the UpdatableCollection
  39.  * serving as the source of the edits, and then apply each undo operation
  40.  * all the way back up to where we are. Subclasses specialize
  41.  * on the exact edit operation to do at each step. 
  42.  * <P>
  43.  * Reconstruction would be two-line recursive procedure of the form:
  44.  * <PRE>
  45.  * UpdatableCollection reconstruct() {
  46.  *   if (the lastest version) return a clone of the held UpdatableCollection
  47.  *   else return edit(nextVersion.reconstruct())
  48.  * }
  49.  * </PRE>
  50.  * Except for two problems:
  51.  *
  52.  * <OL>
  53.  * <LI> We need to prevent interference among concurrent reconstructions
  54.  *    and/or with operations on the collections themselves.
  55.  *    But we cannot afford to hold a lock (synch) on every single node in
  56.  *    the chain of edits at once. For long edit chains, it would 
  57.  *    require too many
  58.  *    simultaneous locks. The java runtime could even run out of them.
  59.  *
  60.  * <LI> The recursion could get very deep, which is not a good idea
  61.  *    in java because of how it uses the stack.
  62.  * </OL>
  63.  * <P>
  64.  * These problems are addressed by:
  65.  * <OL>  
  66.  * <LI> Using a condition variable, that causes each node to
  67.  *    lock without holding all of the locks at once. The
  68.  *    variable used, prevVersion_ happens to be the same
  69.  *    one used for...
  70.  *
  71.  * <LI> Putting next-links from each node to the one representing
  72.  *     the edit which is to follow. This way we can iterate rather
  73.  *     than use recursion. 
  74.  * </OL>
  75.  * <P>
  76.  * (All this would be a little prettier if we offloaded work
  77.  * into Edit Command objects. But since these operations must be
  78.  * coordinated with the Collection nodes, it works better to
  79.  * roll them together.)
  80.  * <P>
  81.  * The code is highly particularized for the operations
  82.  * currently supported in the collections package. It would
  83.  * not be very easy to add subclasses beyond those for the four
  84.  * basic flavors of collection subclasses currently implemented.
  85.  *<P>
  86.  * Some of the basic ideas for this class are due to Mark Miller
  87.  * and unknown people at Xerox Parc.
  88.  * @author Doug Lea
  89.  * @version 0.93
  90.  *
  91.  * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
  92. **/
  93.  
  94. abstract class IncrImpl implements Immutable, Collection {
  95.  
  96. /**
  97.  * The collection performing the actual work. Null if delta'd
  98. **/
  99.  
  100.   protected UpdatableCollection updatable_;
  101.  
  102. /**
  103.  * When delta'd, a ref to the collection we generated.
  104.  * Invariant:  exactly one of updatable_ or nextVersion_ 
  105.  * are non-null at any given time.
  106. **/
  107.  
  108.   protected IncrImpl nextVersion_;
  109.  
  110. /**
  111.  * Ref to the Incr collection that made us (or anyone
  112.  * else requesting an edit operation).
  113.  * Non-null only during reconstructions, so it also
  114.  * serves as a condition variable. When it is non-null,
  115.  * incoming updates must wait. Avoiding back-pointers
  116.  * at other times enables GC to kill off whole chains
  117.  * of nodes that can never be used anyway since their roots are unreferenced.
  118. **/
  119.  
  120.   private IncrImpl prevVersion_;
  121.  
  122. /**
  123.  * Ref to an enumerator that has us pinned. If it is in
  124.  * the midst of a traversal and are performing an
  125.  * incremental operation, we need to make a full clone first.
  126.  * Only one level of pinning supported. If there's more than
  127.  * one, we always conservatively copy.
  128. **/
  129.  
  130.   private IncrCollectionEnumeration pin_;
  131.  
  132. /** 
  133.  * We can only handle a known number of undoable operations on 
  134.  * collections, encoded into op_
  135. **/
  136.  
  137.   protected int op_;
  138.  
  139. /* Known Possible values of op_: */
  140.  
  141.   protected static final int NO_EDIT = 0;
  142.   protected static final int ADD_EDIT = 1;
  143.   protected static final int REMOVE_EDIT = 2;
  144.   protected static final int REPLACE_EDIT = 3;
  145.  
  146.  
  147. /**
  148.  * Some opportunistic sharing: Subclasses happen 
  149.  * to need records of two Object arguments  for updates.
  150. **/
  151.  
  152.   protected Object firstObjectArg_;
  153.   protected Object secondObjectArg_;
  154.  
  155.  
  156.   protected IncrImpl(UpdatableCollection c) { 
  157.     updatable_ = c; 
  158.     nextVersion_ = null;
  159.     prevVersion_ = null;
  160.     op_ = NO_EDIT;
  161.     firstObjectArg_ = null;
  162.     secondObjectArg_ = null;
  163.     pin_ = null;
  164.   }
  165.  
  166. /**
  167.  * Wrapper for clone()
  168.  * @see clone
  169. **/
  170.  
  171.  public Collection duplicate() { 
  172.    Collection c = null;
  173.    try {
  174.      c = (Collection)(this.clone()); 
  175.     } catch (CloneNotSupportedException ex) {}
  176.    return c;
  177.  }
  178.  
  179.  
  180.     
  181. /**
  182.  * Implements collections.Collection.canInclude.
  183.  * @see collections.Collection#canInclude
  184. **/
  185.   public final synchronized boolean     canInclude(Object element) {
  186.     return accessOnly().canInclude(element);
  187.   }
  188.  
  189. /**
  190.  * Implements collections.Collection.isEmpty.
  191.  * @see collections.Collection#isEmpty
  192. **/
  193.   public final synchronized boolean     isEmpty() {
  194.     return accessOnly().isEmpty();
  195.   }
  196.  
  197. /**
  198.  * Implements collections.Collection.size.
  199.  * @see collections.Collection#size
  200. **/
  201.   public final synchronized  int         size() {
  202.     return accessOnly().size();
  203.   }
  204.  
  205.  
  206. /**
  207.  * Implements collections.Collection.includes.
  208.  * @see collections.Collection#includes
  209. **/
  210.   public final synchronized boolean     includes(Object element) {
  211.     return accessOnly().includes(element);
  212.   }
  213.  
  214. /**
  215.  * Implements collections.Collection.occurrencesOf.
  216.  * @see collections.Collection#occurrencesOf
  217. **/
  218.   public final synchronized int         occurrencesOf(Object element) {
  219.     return accessOnly().occurrencesOf(element);
  220.   }
  221.  
  222. /**
  223.  * Implements collections.Collection.sameStructure
  224.  * @see collections.Collection#sameStructure
  225. **/
  226.   public final synchronized boolean  sameStructure(Collection c) {
  227.     return accessOnly().sameStructure(c);
  228.   }
  229.  
  230. /**
  231.  * Implements collections.Collection.elements.
  232.  * @see collections.Collection#elements
  233. **/
  234.   public final synchronized CollectionEnumeration elements() {
  235.     undelta(); 
  236.     // wrap the underlying enumeration in Incr version 
  237.     CollectionEnumeration e = updatable_.elements();
  238.     IncrCollectionEnumeration ie = new IncrCollectionEnumeration(this, e);
  239.     pin(ie);
  240.     return ie;
  241.   }
  242.  
  243.  
  244.   public final synchronized String toString() {
  245.     undelta(); 
  246.     StringBuffer buf = new StringBuffer();
  247.     buf.append("( (class: " + getClass().toString() + ")");
  248.     buf.append(updatable_.toString());
  249.     buf.append(" )");
  250.     return buf.toString();
  251.   }
  252.  
  253.  
  254. /**
  255.  * Call this as the first statement of EVERY subclass method 
  256.  * that performs any kind of constructive update.
  257. **/
  258.  
  259.   protected final synchronized void undelta() {
  260.     if (updatable_ != null) {
  261.  
  262.       if (pin_ != null) { // if pinned, we must conservatively copy
  263.         updatable_ = (UpdatableCollection)(updatable_.duplicate());
  264.         pin_ = null;
  265.       }
  266.  
  267.     }
  268.     else {
  269.  
  270.       // lock everyone while forming the edit chain
  271.       IncrImpl p = linkEditChain(this);
  272.       IncrImpl prev = this;
  273.       IncrImpl base = null;
  274.       while (p != null) {
  275.         IncrImpl nxt = p.linkEditChain(prev);
  276.         if (nxt == null) {
  277.           base = p;
  278.           break;
  279.         }
  280.         else {
  281.           prev = p;
  282.           p = nxt;
  283.         }
  284.       }
  285.  
  286.       // loop through the edits
  287.       UpdatableCollection c = null;
  288.       p = base;
  289.       // funny end-condition on loop:
  290.       //    since we've used up null as a sentinel, we go until
  291.       //    we are back at our own node.
  292.       for (;;) { 
  293.         c = p.reconstruct(c);
  294.         IncrImpl nxt = p.breakEditChain();
  295.         if (p == this) break;
  296.         else p = nxt;
  297.       }
  298.       // Reset instance variables to use new updatable_
  299.       updatable_ = c;
  300.       nextVersion_ = null;
  301.       op_ = NO_EDIT;
  302.       firstObjectArg_ = null;
  303.       secondObjectArg_ = null;
  304.       pin_ = null;
  305.     }
  306.   }
  307.  
  308. /**
  309.  * Special case of undelta that avoids the pin-check
  310.  * in cases where we are performing only non-mutative operations
  311. **/
  312.    protected final UpdatableCollection accessOnly() {
  313.      if (updatable_ == null) undelta();
  314.      return updatable_;
  315.    }
  316.        
  317.  
  318. /**
  319.  * unpin from a traversal. Called only by IncrCollectionEnumeration
  320.  * when hasMoreElements() is false.
  321. **/
  322.   
  323.   synchronized final void unpin(IncrCollectionEnumeration e) {
  324.     if (e == pin_) pin_ = null;
  325.   }
  326.  
  327. /**
  328.  * Pin during a traversal. Call from any method constructing an
  329.  * enumeration.
  330. **/
  331.   
  332.   protected synchronized final void pin(IncrCollectionEnumeration e) {
  333.     pin_ = e;
  334.   }
  335.  
  336. /**
  337.  * Must implement in subclasses to perform subclass-specific edits
  338. **/
  339.  
  340.   protected abstract UpdatableCollection doEdit(UpdatableCollection c);
  341.  
  342. /**
  343.  * Do a step of reconstruction. handle cloning cases, else pass off
  344.  * to doEdit
  345. **/
  346.  
  347.   private synchronized UpdatableCollection reconstruct(UpdatableCollection c) {
  348.     if (updatable_ != null) { // we have a source
  349.       return (UpdatableCollection)(updatable_.duplicate());
  350.     }
  351.     else if (op_ == NO_EDIT) 
  352.       return c;
  353.     else
  354.       return doEdit(c);
  355.   }
  356.  
  357.  
  358. /**
  359.  * Handle the locking mechanics while making edit chains
  360. **/
  361.  
  362.   private synchronized IncrImpl linkEditChain(IncrImpl nxt) {
  363.     if (prevVersion_ != null) {
  364.       do {
  365.         try { wait(); }
  366.         catch (InterruptedException ex) { } // safe to ignore because of recheck
  367.       } while (prevVersion_ != null);
  368.     }
  369.     prevVersion_ = nxt;
  370.     return nextVersion_;
  371.   }
  372.  
  373. /**
  374.  * Handle the locking mechanics while breaking edit chains
  375. **/
  376.   private synchronized IncrImpl breakEditChain() {
  377.     IncrImpl s = prevVersion_;
  378.     prevVersion_ = null;
  379.     notifyAll();
  380.     return s;
  381.   }
  382.  
  383. /**
  384.  * Implements collections.ImplementationCheckable.assert.
  385.  * @see collections.ImplementationCheckable#assert
  386. **/
  387.   public void assert(boolean pred) 
  388.   throws ImplementationError {
  389.     ImplementationError.assert(this, pred);
  390.   }
  391.  
  392.  
  393. /**
  394.  * Implements collections.ImplementationCheckable.checkImplementation.
  395.  * @see collections.ImplementationCheckable#checkImplementation
  396. **/
  397.   public synchronized void checkImplementation()
  398.   throws ImplementationError {
  399.     assert(((updatable_ == null) != (nextVersion_ == null)));
  400.     assert(prevVersion_ == null);
  401.     assert((op_ >= NO_EDIT) && (op_ <= REPLACE_EDIT));
  402.  
  403.     if (updatable_ != null) 
  404.       updatable_.checkImplementation();
  405.     else 
  406.       nextVersion_.checkImplementation();
  407.   }
  408.  
  409. }
  410.  
  411.